package com.sise.Array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *      15. 三数之和
 *
 *      给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 *      注意：答案中不可以包含重复的三元组。
 *
 *      输入：nums = [-1,0,1,2,-1,-4]
 *      输出：[[-1,-1,2],[-1,0,1]]
 *
 *      题解：一开始以为是 回溯算法，并且可以求出值，但没有去重，所以就停止了。
 *
 *      这里是怎么去重的？利用 排序 后，确定基数，另外两位数在其右边，故此不会有重复的情况
 *      使用 for 循环，使得每个数值都可以作为基数，然后利用 [left,right] 的区间，求得三数之和，如果大于0，说明 right 太大了，如果小于 0，那么 left 太小了，
 *      对于此操作，使用的是 while 循环直到不满足条件
 *
 */
public class _15_threeSum {

    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);                                          // 对数组进行排序，方便后续判断当前值是否大于 0

        List<List<Integer>> res = new ArrayList<>();
        for (int k = 0; k < nums.length - 2; k++) {                 // 由于节点不能相同，本来是 length - 1 变成 length - 2
            if (nums[k] > 0) break;                                 // 剪枝 - 如果当前值已经大于 0，那么它右边数值相加必大于 0
            if (k > 0 && nums[k] == nums[k - 1]) continue;          // 相同数值跳过 - 如果当前值与上一个值相等，那么就跳过，防止同一个值相加多次
            int left = k + 1;                                       // 以当前值为基点，在 k+1， length-1 找到两位数向中间缩进
            int right = nums.length - 1;

            while (left < right) {                                  // 当左右相交就停止
                int sum = nums[k] + nums[left] + nums[right];       // 将当前值、left、right 相加

                if (sum < 0) {                                              // 如果三数之和小于0，那么 left 应该向右移动（这里利用 while 循环，如果 ++left 等于 left，那么就继续往下遍历）
                    while (left < right && nums[left] == nums[++left]) ;
                } else if (sum > 0) {                                       // 如果三数之和大于0，那么 right 应该向左移动
                    while (left < right && nums[right] == nums[--right]) ;
                } else {                                                    // 如果三数之和等于0.那么就将其组成 List，添加到 result 中
                    res.add(new ArrayList<>(Arrays.asList(nums[k], nums[left], nums[right])));
                    while (left < right && nums[left] == nums[++left]) ;
                    while (left < right && nums[right] == nums[--right]) ;
                }
            }
        }
        return res;
    }
}